|
In graph theory, an edge dominating set for a graph ''G'' = (''V'', ''E'') is a subset ''D'' ⊆ ''E'' such that every edge not in ''D'' is adjacent to at least one edge in ''D''. An edge dominating set is also known as a ''line dominating set''. Figures (a)–(d) are examples of edge dominating sets (thick red lines). A minimum edge dominating set is a smallest edge dominating set. Figures (a) and (b) are examples of minimum edge dominating sets (it can be checked that there is no edge dominating set of size 2 for this graph). == Properties == An edge dominating set for ''G'' is a dominating set for its line graph ''L''(''G'') and vice versa. Any maximal matching is always an edge dominating set. Figures (b) and (d) are examples of maximal matchings. Furthermore, the size of a minimum edge dominating set equals the size of a minimum maximal matching. A minimum maximal matching is a minimum edge dominating set; Figure (b) is an example of a minimum maximal matching. A minimum edge dominating set is not necessarily a minimum maximal matching, as illustrated in Figure (a); however, given a minimum edge dominating set ''D'', it is easy to find a minimum maximal matching with |''D''| edges (see, e.g., ). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Edge dominating set」の詳細全文を読む スポンサード リンク
|